def heapify(arr, n, i):
    biggest=i
    l=i*2+1
    r=i*2+2
    if l<n and arr[l]>arr[biggest]:
        biggest=l
    if r<n and arr[r]>arr[biggest]:
        biggest=r
    if biggest!=i:
        arr[i],arr[biggest]=arr[biggest],arr[i]
        heapify(arr,n,biggest)



def heap_sort(arr):
    n=len(arr)
    for i in range(n//2-1,-1,-1):
        heapify(arr,n,i)
    for i in range(n-1,-1,-1):
        arr[0],arr[i]=arr[i],arr[0]
        heapify(arr,i,0)



# 🎉 示例用法
arr = [3, 1, 5, 8, 2, 9, 4]
heap_sort(arr)
print("排完序的数组喵~: ", arr)
